package com.yin.myproject.arithmetic;

import java.util.concurrent.ConcurrentHashMap;

/**
 * 基于数组实现一个树
 * @author Eason
 * @create 2018-04-25 10:35
 **/
public class ArrayTree<T> {

    //默认树大小
    private static final int DEFAULT_TREE_SIZE = 50;
    //使用一个数组存放元素
    private Node[] nodes;
    //树的大小
    private int treeSize;
    //树的节点数量
    private int nodesNum;
    //根节点元素
    private Node<T> root;

    /**
     * 通过指定树的大小创建一棵空树
     *
     * @param treeSize
     */
    public ArrayTree(int treeSize) {
        this.treeSize = treeSize;
    }

    /**
     * 通过指定根节点元素创建一棵空树,树的大小为默认值
     *
     * @param root
     */
    public ArrayTree(Node<T> root) {
        this.root = root;
        nodes = new Node[DEFAULT_TREE_SIZE];
    }

    /**
     * 通过指定根节点元素和树的大小创建一棵树
     *
     * @param treeSize
     * @param root
     */
    public ArrayTree(int treeSize, Node<T> root) {
        this.treeSize = treeSize;
        this.root = root;
        nodes = new Node[treeSize];
        nodes[0] = root;
    }

    /**
     * 判断根节点是否存在
     *
     * @return
     */
    private boolean hasRootNode() {
        return root != null;
    }

    /**
     * 返回某个节点在数组中的位置索引,不存在返回-1
     *
     * @param node
     * @return
     */
    private int positionOfNode(Node node) {
        for (int i = 0; i < nodesNum; i++) {
            if (nodes[i] == node) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 向指定父节点下追加子节点
     *
     * @param data
     * @param parent
     * @return
     */
    public Node addNode(T data, Node parent) {
        if (!hasRootNode()) {
            throw new RuntimeException("根节点不存在");
        }
        int position = positionOfNode(parent);
        if (position != -1) {
            if (nodesNum++ > DEFAULT_TREE_SIZE) {
                //TODO:动态扩容
                throw new RuntimeException("树已满");
            }
            nodes[nodesNum] = new Node<>(data, position);
        } else {
            throw new RuntimeException("父节点不存在");
        }
        return nodes[nodesNum];
    }

    public static class Node<E> {
        //元素内容
        E data;
        //父节点所在的数组索引
        int parent;

        public Node() {
        }

        public Node(E data) {
            this.data = data;
        }

        public Node(E data, int parent) {
            this.data = data;
            this.parent = parent;
        }

        public E getData() {
            return data;
        }

        public void setData(E data) {
            this.data = data;
        }

        public int getParent() {
            return parent;
        }

        public void setParent(int parent) {
            this.parent = parent;
        }

        @Override
        public String toString() {
            return "ArrayTree$Node{" +
                    "data=" + data +
                    ", parent=" + parent +
                    '}';
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Node<?> node = (Node<?>) o;

            if (parent != node.parent) return false;
            return data != null ? data.equals(node.data) : node.data == null;
        }

        @Override
        public int hashCode() {
            int result = data != null ? data.hashCode() : 0;
            result = 31 * result + parent;
            return result;
        }
    }

    public static void main(String[] args) {
        ConcurrentHashMap<String,String> concurrentHashMap = new ConcurrentHashMap<>(35);
    }
}
